﻿#define _CRT_SECURE_NO_WARNINGS 1

// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

#include <iostream>
#include <stack>
using namespace std;

#include <assert.h>

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        if (root == nullptr)
            return false;
        // 前序遍历的思路，找x结点的路径
        // 遇到root结点先push⼊栈，因为root就算不是x
        // 但是root可能是根->x路径中⼀个分⽀结点
            path.push(root);
        if (root == x)
            return true;
        if (GetPath(root->left, x, path))
            return true;
        if (GetPath(root->right, x, path))
            return true;

        // 如果左右⼦树都没有x，那么说明上⾯⼊栈的root不是根->x路径中⼀个分⽀结点
        // 所以要pop出栈，回退，继续去其他分⽀路径进⾏查找
        path.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath, qPath;
        GetPath(root, p, pPath);
        GetPath(root, q, qPath);
        // 模拟链表相交，两个路径找交点
        // ⻓的先⾛差距步，再⼀起⾛找交点
        while (pPath.size() != qPath.size())
        {
            if (pPath.size() > qPath.size())
                pPath.pop();
            else
                qPath.pop();
        }
        while (pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }
};

int main()
{
    // root = [3,5,1,6,2,0,8,null,null,7,4]
    TreeNode* root = new TreeNode(3);

    root->left = new TreeNode(5);
    root->right = new TreeNode(1);

    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);

    root->left->right->left = new TreeNode(7);
    root->left->right->left = new TreeNode(4);

    auto p = root->left, q = root->right;

    cout << root << endl;
    cout << Solution().lowestCommonAncestor(root, p, q) << endl;

    return 0;
}



